package jhx;

/**
 * Linked List (with circular iterator)
 * 
 * coded for haxe-2.06 and neko-1.8.1/hxcpp-2.06.1
 *
 * developed for "Search for TSP quick solution" personal project
 * 
 * must yet be properly tested
 * 
 * @author Jonas Malaco Filho
 * @version 1.11
 * 
 * Copyright (c) 2010 Jonas Tadeu Silva Malaco Filho <jonasmalacofilho@gmail.com>
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 * 
 */

class LList<T>
{
	public var head(default, null):LListNode<T>;
	public var length(default, null):Int;
	
	public function new() 
	{
		head = null;
		length = 0;
	}
	
	/**
	 * Pushs an object to the start of the list
	 */
	public inline function push(__list__obj:T)
	{
		switch (head) {
			case null: 
				head = new LListNode<T>(__list__obj, null);
			default: 
				head = new LListNode<T>(__list__obj, head);
		}
		length++;
	}
	
	public inline function mpush(__list__obj:T)
	{
		switch (head) {
			case null: 
				head = new LListNode<T>(__list__obj, null);
			default: 
				head = new LListNode<T>(__list__obj, head);
		}
		length++;
		return head;
	}
	
	public inline function first()
	{
		return switch (head) {
			case null:
				null;
			default:
				head.obj;
		};
	}
	
	public inline function mfirst()
	{
		return head;
	}
	
	public inline function isEmpty()
	{
		return switch (head) {
			case null:
				true;
			default:
				false;
		};
	}
	
	public inline function clear()
	{
		head = null;
		length = 0;
	}
	
	/**
	 * Pops the first element of the list
	 */
	public inline function pop()
	{
		return switch (head) {
			case null:
				null;
			default:
				var obj = head.obj;
				head = head.next;
				length--;
				obj;
		};
	}
	
	public function remove(obj:T)
	{
		var current = head;
		var previous = null;
		var sucess = false;
		while (
			switch (current) {
				case null: false;
				default:
					if (current.obj == obj) {
						current = current.mkill();
						switch (previous) {
							case null:
								head = current;
							default:
								previous.next = current;
						}
						length--;
						sucess = true;
						false;
					}
					else {
						previous = current;
						current = current.next;
						true;
					}
			}
		) { }
		return sucess;
	}
	
	public inline function insertAfter(__list__obj:T, __list__ref:LListNode<T>)
	{
		switch (__list__ref) {
			case null:
			default:
				length++;
				__list__ref.next = new LListNode<T>(__list__obj, __list__ref.next);
		};
	}
	
	public inline function minsertAfter(__list__obj:T, __list__ref:LListNode<T>)
	{
		return switch (__list__ref) {
			case null:
				null;
			default:
				length++;
				__list__ref.next = new LListNode<T>(__list__obj, __list__ref.next);
		};
	}
	
	public inline function replace(__list__obj:T, __list__ref:LListNode<T>)
	{
		switch (__list__ref) {
			case null:
				null;
			default:
				__list__ref.obj = __list__obj;
		};
	}
	
	public function mfind(obj:T)
	{
		var current = head;
		while (
			switch (current) {
				case null:
					current = null;
					false;
				default:
					if (current.obj == obj) {
						false;
					}
					else {
						current = current.next;
						true;
					}
			}
		) { }
		return current;
	}
	
#if cpp
	public function iterator():Iterator<T>
	{
		return new LListIterator<T>(head);
	}
	public function citerator():Iterator<T>
	{
		return new CLListIterator<T>(head);
	}
#else
	public function iterator():Iterator<T>
	{
		var next = head;
		return {
			hasNext: function() { return next != null; },
			next: function() {
				//return switch (next) {
					//case null:
						//null;
					//default: 
						//var obj = next.obj;
						//next = next.next;
						//obj;
				//};
				var obj = next.obj;
				next = next.next;
				return obj;
			}
		};
	}
	public function citerator():Iterator<T>
	{
		var myHead = head;
		var next = head;
		var circular = false;
		return {
			hasNext: function() {
				return (next != null || !circular);
			},
			next: function() {
				return switch (next) {
					case null:
						circular = true;
						switch (myHead) {
							case null: null;
							default: myHead.obj;
						}
					default:
						var obj = next.obj;
						next = next.next;
						obj;
				};
			}
		};
	}
#end

	public function join(sep:String)
	{
		var s = new StringBuf();
		var first = true;
		var cur = head;
		while(cur != null) {
			if(first)
				first = false;
			else
				s.add(sep);
			s.add(Std.string(cur.obj));
			cur = cur.next;
		}
		return s.toString();
	}
	
	public function cjoin(sep:String)
	{
		var s = new StringBuf();
		var first = true;
		var cur = head;
		while(cur != null) {
			if(first)
				first = false;
			else
				s.add(sep);
			s.add(Std.string(cur.obj));
			cur = cur.next;
		}
		s.add(sep);
		s.add(Std.string(head.obj));
		return s.toString();
	}
	
	public function toString()
	{
		var s = new StringBuf();
		var first = true;
		var cur = head;
		s.add("[" + Std.string(length) + "] {");
		while(cur != null) {
			if(first)
				first = false;
			else
				s.add(", ");
			s.add(Std.string(cur.obj));
			cur = cur.next;
		}
		s.add("}");
		return s.toString();
	}
	
	public function ctoString()
	{
		var s = new StringBuf();
		var first = true;
		var cur = head;
		s.add("[" + Std.string(length) + "] {");
		while(cur != null) {
			if(first)
				first = false;
			else
				s.add(", ");
			s.add(Std.string(cur.obj));
			cur = cur.next;
		}
		s.add(", ");
		s.add(Std.string(head.obj));
		s.add("}");
		return s.toString();
	}
	
	public static function rlist<A>(it:Iterable<A>)
	{
		var a = new LList<A>();
		for (i in it) {
			switch (a.head) {
				case null: 
					a.head = new LListNode<A>(i, null);
				default: 
					a.head = new LListNode<A>(i, a.head);
			}
			a.length++;
		}
		return a;
	}
	
	public static function list<A>(it:Iterable<A>)
	{
		var a = new LList<A>();
		var last:LListNode<A> = null;
		for (i in it) {
			switch (last) {
				case null: 
					last = a.head = new LListNode<A>(i, null);
				default: 
					last = last.next = new LListNode<A>(i, null);
			}
			a.length++;
		}
		return a;
	}
	
	public static function map<A, B>(it:Iterable<A>, f:A->B)
	{
		var a = new LList<B>();
		var last:LListNode<B> = null;
		for (i in it) {
			switch (last) {
				case null: 
					last = a.head = new LListNode<B>(f(i), null);
				default: 
					last = last.next = new LListNode<B>(f(i), null);
			}
			a.length++;
		}
		return a;
	}
	
	public function omap<B>(f:T->B)
	{
		var a = new LList<B>();
		var last:LListNode<B> = null;
		var cur = head;
		while (cur != null) {
			switch (last) {
				case null: 
					last = a.head = new LListNode<B>(f(cur.obj), null);
				default: 
					last = last.next = new LListNode<B>(f(cur.obj), null);
			}
			a.length++;
			cur = cur.next;
		}
		return a;
	}
	
	public static function mapi<A, B>(it:Iterable<A>, f:Int->A->B)
	{
		var a = new LList<B>();
		var last:LListNode<B> = null;
		var j = 0;
		for (i in it) {
			switch (last) {
				case null: 
					last = a.head = new LListNode<B>(f(j++, i), null);
				default: 
					last = last.next = new LListNode<B>(f(j++, i), null);
			}
			a.length++;
		}
		return a;
	}
	
	public function omapi<B>(f:Int->T->B)
	{
		var a = new LList<B>();
		var last:LListNode<B> = null;
		var cur = head;
		var j = 0;
		while (cur != null) {
			switch (last) {
				case null: 
					last = a.head = new LListNode<B>(f(j++, cur.obj), null);
				default: 
					last = last.next = new LListNode<B>(f(j++, cur.obj), null);
			}
			cur = cur.next;
		}
		a.length = j;
		return a;
	}
	
/*
	public static function circularFold<A, B>(it:LList<A>, f:A->B->B, first:B)
	{
		for (i in it.circularIterator())
			first = f(i, first);
		return first;
	}
	
	public static function circularIter<A>(it:LList<A>, f:A->Void)
	{
		for(x in it.circularIterator())
			f(x);
	}
*/
	
	/**
	 * Fold
	 */
	public function fold<B>(f:T->B->B, first:B)
	{
		var cur = head;
		while (cur != null) {
			first = f(cur.obj, first);
			cur = cur.next;
		}
		return first;
	}
	
	/**
	 * Circular fold
	 */
	public function cfold<B>(f:T->B->B, first:B)
	{
		var cur = head;
		while (cur != null) {
			first = f(cur.obj, first);
			cur = cur.next;
		}
		first = f(head.obj, first);
		return first;
	}
	
	/**
	 * Iterate
	 */
	public function iter(f:T->Void)
	{
		var cur = head;
		while (cur != null) {
			f(cur.obj);
			cur = cur.next;
		}
	}
	
	/**
	 * Ciruclar iterate
	 */
	public function citer(f:T->Void)
	{
		var cur = head;
		while (cur != null) {
			f(cur.obj);
			cur = cur.next;
		}
		f(head.obj);
	}
	
	/**
	 * Internal manipulation iterate
	 */
	public function miter(f:LListNode<T>->LListNode<T>->Void)
	{
		var cur = head;
		while (cur != null) {
			f(cur, cur.next);
			cur = cur.next;
		}
	}
	
	/**
	 * Circular internal manipulation iterate
	 */
	public function cmiter(f:LListNode<T>->LListNode<T>->Void)
	{
		var cur = head;
		while (cur != null) {
			switch (cur.next) {
				case null: f(cur, head);
				default:
					f(cur, cur.next);
			}
			cur = cur.next;
		}
	}
	
	/**
	 * Returns a clone for this list - Objects <T> are cloned with Reflection
	 */
	public function iclone()
	{
		var a = new LList<T>();
		var last:LListNode<T> = null;
		var cur = head;
		while (cur != null) {
			switch (last) {
				case null: 
					a.head = new LListNode<T>(Reflect.copy(cur.obj), null);
					last = a.head;
				default: 
					last = last.next = new LListNode<T>(Reflect.copy(cur.obj), null);
			}
			a.length++;
			cur = cur.next;
		}
		return a;
	}
	
	/**
	 * Returns a clone for this list structure - optimized list(this)
	 */
	public function copy()
	{
		var a = new LList<T>();
		var last:LListNode<T> = null;
		var cur = head;
		while (cur != null) {
			switch (last) {
				case null: 
					a.head = new LListNode<T>(cur.obj, null);
					last = a.head;
				default: 
					last = last.next = new LListNode<T>(cur.obj, null);
			}
			a.length++;
			cur = cur.next;
		}
		return a;
	}
	
	/**
	 * Returns a reverse list for this one
	 */
	public function rev()
	{
		var a = new LList<T>();
		var cur = head;
		while (cur != null) {
			switch (a.head) {
				case null: 
					a.head = new LListNode<T>(cur.obj, null);
				default: 
					a.head = new LListNode<T>(cur.obj, a.head);
			}
			a.length++;
			cur = cur.next;
		}
		return a;
	}
	
	public function filter(f:T->Bool)
	{
		var a = new LList<T>();
		var last:LListNode<T> = null;
		var cur = head;
		while (cur != null) {
			if (f(cur.obj)) {
				switch (last) {
					case null: 
						last = a.head = new LListNode<T>(cur.obj, null);
					default: 
						last = last.next = new LListNode<T>(cur.obj, null);
				}
				a.length++;
			}
			cur = cur.next;
		}
		return a;
	}
	
	/**
	 * Concatenate (destroys previous lists)
	 * list1, list2 -> list(1-2)
	 */
	public function concat(list:LList<T>)
	{
		var a = new LList<T>();
		var cur = head;
		if (cur != null) {
			// get last node
			while (cur.next != null) cur = cur.next;
			cur.next = list.head;
			a.head = head;
			// clear original lists step
			head = null;
		}
		else {
			a.head = list.head;
		}
		a.length = length + list.length;
		// clear original lists step
		list.head = null;
		length = 0; list.length = 0;
		return a;
	}
	
	//public function destroy()
	//{
		//throw "not implemented - will destroy this list and also clear its nodes";
	//}

	/**
	 * Test routines
	 */
/*
	public static function test()
	{
		var a = new LList<Int>();
		trace("push tests");
		a.push(1);
		a.push(2);
		a.push(3);
		a.push(4);
		a.push(5);
		a.push(6);
		trace(a);
		trace("getHead test");
		trace(a.first());
		trace("iterator test");
		for (aa in a) {
			trace(aa);
		}
		trace("circular iterator test");
		for (aa in a.citerator()) {
			trace(aa);
		}
		trace("toString");
		trace(a);
		trace("circularToString");
		trace(a.ctoString());
		trace("removal tests");
		trace("remove 1"); a.remove(1); trace(a);
		trace("remove 5"); a.remove(5); trace(a);
		trace("remove 6"); a.remove(6); trace(a);
		trace("remove 6"); a.remove(6); trace(a);
		trace("remove 3"); a.remove(3); trace(a);
		trace("remove 4"); a.remove(4); trace(a);
		trace("remove 6"); a.remove(6); trace(a);
		trace("remove 2"); a.remove(2); trace(a);
		trace("remove 1"); a.remove(1); trace(a);
		trace("push 1-6");
		a.push(1);
		a.push(2);
		var node_3 = a._obj_node_push(3);
		var node_4 = a._obj_node_push(4);
		var node_5 = a._obj_node_push(5);
		a.push(6);
		trace(a);
		trace("insert 2 after node_3");
		trace(node_3);
		trace(a._obj_node_void_insertAfter(2, node_3));
		trace(a);
		trace("insert 3 after node_5"); trace(a._obj_node_node_insertAfter(3, node_5));
		trace(a);
		trace("replace node_4 for 7"); trace(a._obj_node_void_replace(7, node_4));
		trace(a);
		trace("find 5"); trace(a._obj_node_find(5));
		trace("Lambda");
		var b = Lambda.array(a);
		var c = LList.list(b);
		trace(c);
		var d = LList.revList(b);
		trace(d);
		trace(Lambda.array(c.circularIterator()));
	}
*/
}

class LListNode<T>
{
	public var next:LListNode<T>;
	public var obj:T;
	public inline function new(obj:T, next:LListNode<T>)
	{
		this.obj = obj;
		this.next = next;
	}
	/**
	 * Clears all properties
	 */
	public inline function clear()
	{
		this.obj = null;
		this.next = null;
	}
	/**
	 * Clears all properties and returns the pointer for the next node
	 */
	public inline function mkill()
	{
		var __mkill__dead = this.next;
		this.obj = null;
		this.next = null;
		return __mkill__dead;
	}
	
	public function toString()
	{
		var __temp__s = new StringBuf();
		__temp__s.add("{obj: ");
		__temp__s.add(Std.string(obj));
		__temp__s.add(", next: ");
		__temp__s.add(Std.string(switch (next) { case null: null; default: next.obj; } ));
		__temp__s.add("}");
		return __temp__s.toString();
	}
	
}

#if cpp
class LListIterator<T> extends cpp.FastIterator<T>
{
	var nx:LListNode<T>;
	override public function hasNext():Bool { return nx != null; }
	override public function next():T {
			//return switch (nx) {
				//case null:
					//null;
				//default: 
					//var obj = nx.obj;
					//nx = nx.next;
					//obj;
			//}; }
			var obj = nx.obj;
			nx = nx.next;
			return obj; }
	public function new(head) { nx = head; }
}
class CLListIterator<T> extends cpp.FastIterator<T>
{
	var hd:LListNode<T>;
	var nx:LListNode<T>;
	var circular:Bool;
	override public function hasNext():Bool { return (nx != null || !circular); }
	override public function next():T {
		return switch (nx) {
			case null:
				circular = true;
				switch (hd) {
					case null: null;
					default: hd.obj;
				}
			default:
				var obj = nx.obj;
				nx = nx.next;
				obj;
		}; }
	public function new(head)
	{
		hd = head;
		nx = head;
		circular = false;
	}
}
#end